package club.xiaojiawei.dp;

import java.util.*;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/5/22 2:46 PM
 * @question 139. 单词拆分
 * @description 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
 * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
 */
public class WordBreak139 {

    public static void main(String[] args) {
        WordBreak139 test = new WordBreak139();
        boolean result = test.wordBreak("catsandog", Arrays.asList("cats", "dog", "sand", "and", "cat"));
        System.out.println(result);
    }

    /**
     * 递归回溯-超时
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        set = new HashSet<>(wordDict);
        return recursion(s, wordDict);
    }

    HashSet<String> set;

    public boolean recursion(String s, List<String> wordDict){
        if (s.equals("")){
            return true;
        }
        for (String s1 : wordDict) {

        }
        return false;
    }

    /**
     * 官方-dp
     * 时间复杂度 O(n^2)
     * 空间复杂度 O(n)
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak2(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    /**
     * 民间-dp优化
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak3(String s, List<String> wordDict) {
        int maxLen = 0;
        Set<String> set = new HashSet<>();
        for (String word : wordDict) {
            set.add(word);
//            获取字典中最长单词的长度
            maxLen = Math.max(maxLen, word.length());
        }
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for (int i = 1; i <= len; i++) {
//            如果substring的长度大于单词最长长度时便没必要继续循环
            for (int j = i; j >= 0 && j >= i - maxLen; j--) {
                if (set.contains(s.substring(j, i)) && dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }

    /**
     * 民间-递归回溯（记忆搜索）
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak4(String s, List<String> wordDict) {
//        dp[i]表示以下标i开始截取的字符串是否能被单词拼出，0表示初始状态，即未判断的，1表示能，2表示不能
        int[] dp=new int[s.length() + 1];
        dp[s.length()] = 1;
        return can(s, wordDict, 0, dp);
    }
    public boolean can(String s, List<String> wordDict, int start, int[] dp){
        if(dp[start] == 0){
            boolean res = false;
            for(int i = 0; i < wordDict.size(); i++){
                if(check(s, start, wordDict.get(i))){
                    res = can(s, wordDict, start+wordDict.get(i).length(), dp);
                    if(res) break;
                }
            }
            if(res) dp[start] = 1;
            else dp[start] = 2;
        }
        return dp[start] == 1;
    }

//    相当于startWith();
    public boolean check(String s,int start,String b){
        if(s.length() - start < b.length())
            return false;
        for(int i = 0; i < b.length(); i++){
            if(s.charAt(start + i) != b.charAt(i))
                return false;
        }
        return true;
    }
}
